#include <vector>
#include <string>
#include <unordered_set>
using namespace std;

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return string字符串vector
     */
    vector<string> Permutation(string str) {
        vector<string> result;
        if (str.empty()) {
            return result;
        }
        unordered_set<string> result_set;
        dfs("", str, result_set);
        for (auto& item : result_set) {
            result.emplace_back(std::move(item));
        }
        return result;
    }

    void dfs(string prefix, string remain, unordered_set<string>& result) {
        if (remain.empty()) {
            result.insert(prefix);
            return;
        }
        for (int i = 0; i < remain.size(); ++i) {
            string new_prefix = prefix + remain[i];
            string new_remain = remain.substr(0, i) + remain.substr(i + 1);
            dfs(new_prefix, new_remain, result);
        }
    }
};